package com.demo.sort;

import java.util.Arrays;

public class HeapSort {


    public static void main(String[] args) {
        int[] arr = {6,4,8,4,1,3,5};
        arr = healSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static int len;
    public static int[] healSort(int[] arr) {
        len = arr.length;
        if(len<1){
            return  arr;
        }
        buildMaxHeap(arr);
        while (len>0){
            swap(arr,0,len-1);
            len--;
            adjustHeap(arr,0);
        }
        return arr;
    }


    public static void buildMaxHeap(int[] arr) {
        for (int i = (len / 2 - 1); i >= 0; i--) {
            adjustHeap(arr,i);
        }
    }

    public static void adjustHeap(int[] arr, int i) {
        int maxIndex = i;
        //如果有左子树
        if (i * 2 < len && arr[i * 2] > arr[maxIndex]) {
            maxIndex = i * 2;
        }

        if (i * 2 + 1 < len && arr[i * 2 + 1] > arr[maxIndex]) {
            maxIndex = i * 2 + 1;
        }
        if (maxIndex != i) {
            swap(arr, maxIndex, i);
            adjustHeap(arr, maxIndex);
        }


    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
